/// @tags:
#include <cstdio>
#include <iostream>

using namespace std;

namespace BlueQuantum {

typedef long long ll;

int const M = 5e7;

int n, m;

inline ll solve() {
  ll fi1, fi2, f;
  cin >> fi2 >> fi1;
  fi2 %= m, fi1 %= m;
  if (fi2 == 0) return 0;
  if (fi1 == 0) return 1;
  for (int j = 0, lim = M / n; j < lim; ++j) {
    f = fi1 + fi2;
    if (f >= m) f -= m;
    if (f == 0) return j + 2;
    fi2 = fi1, fi1 = f;
  }
  return -1;
}

inline int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) { cout << solve() << '\n'; }
  return 0;
}

}  // namespace BlueQuantum
int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("fib.in", "r", stdin);
  freopen("fib.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
